package com.leetcode;


import java.util.LinkedList;
import java.util.List;

public class Leetcode300 {
    /*
    //solution 1: 动态规划
    // 动态规划两部曲：
    //          1) 状态定义：dp[i]: 从0->i 的最长子序列的长度
    //          2）动态转移方程: dp[j]代表 dp[i]的子序列的长度, j的值范围是 0->i-1,dp[i] = Max{dp[j]} +1
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int n = nums.length;
        int[] dp = new int[n];
        //至少包含一个数，最小长度是1
        int res = 1;
        //dp[i]的最小长度是1
        for(int i=0; i<n; i++){
            dp[i] = 1;
        }

        for(int i=0; i<n; i++){
            //j是i的子序列，因此 j 范围是: 0->i-1
           for(int j=0; j<i; j++){
               //如果nums[j] < nums[i],代表j 是 i的子序列
              if(nums[j] < nums[i]){
                  //dp[j]代表不同的子序列，不同的子序列长度不同，取最长的子序列
                 dp[i] = Math.max(dp[i],dp[j]+1);
              }

              //不同的序列长度不同，去最长的子序列
              res = Math.max(res,dp[i]);
           }
        }

        return res;
    }
*/
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        List<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            int lower = binarySearch(list, nums[i]);
            if (lower == list.size()) {
                list.add(nums[i]);
            } else {
                list.set(lower, nums[i]);
            }
        }
        return list.size();
    }

    public static int binarySearch(List<Integer> list, int key) {
        int low = 0;
        int high = list.size() - 1;
        while (high >= low) {
            int mid = (low + high) / 2;
            if (key <= list.get(mid))
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }

    public static void main(String[] args) {
//        int[] nums = {4, 10, 4, 3, 8, 9};
//        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int[] nums = {0, 1, 0, 3, 2, 3};
        Leetcode300 leetcode = new Leetcode300();
        System.out.println(leetcode.lengthOfLIS(nums));
    }
}
